/**
 * @file graphe.c
 * @brief Fichier source du module graphe
 *
 * @author Rachid Delory
 * @version 1.0
 */

#include "graphe.h"


void initGrapheVide(Graphe * g)
{
  if(g)
    {
      Liste * listeNoeud = (Liste*) malloc(sizeof(Liste));
      Liste * listeArc = (Liste*) malloc(sizeof(Liste));
      g->listeNoeud = listeNoeud;
      g->listeArc = listeArc;
      initialise_Liste(g->listeNoeud,creerCopie_Noeud, detruire_Noeud, afficher_Noeud, comparer_Noeud);
      initialise_Liste(g->listeArc, creerCopie_Arc, detruire_Arc, afficher_Arc, comparer_Arc);
    }
  else
    printf("erreur le graphe n'existe pas\n");
}

void testamentGraphe(Graphe * g)
{
  if(g != NULL)
    {
      testament_Liste(g->listeNoeud);
      testament_Liste(g->listeArc);
      free(g->listeNoeud);
      free(g->listeArc);
      g->listeNoeud = NULL;
      g->listeArc = NULL;
    }
}

int ajoutGrapheNoeud(Graphe * g, char * nom)
{
  if(g)
    {
      Noeud res;
      int nomExist;
      init_Noeud(&res, nom);
      nomExist = chercheElem_Liste(&res, g->listeNoeud);
      if(nomExist == 1)
	return 1;
      insereEnQueue_Liste(&res, g->listeNoeud);
      testament_Noeud(&res);
    }
  return 0;
  /* 1: noeud deja existant ; 0: noeud creer et ajoute */ 
}

int suppressionGrapheNoeudParNom(Graphe * g, char * nom)
{
  if(g)
    {
      Noeud res;
      int nomExist;
      init_Noeud(&res,nom);
	
      nomExist = chercheElem_Liste(&res, g->listeNoeud);

      if(nomExist == 1)
	{
	  int i;
	  Arc * arc = creer_Arc(0,&res,&res);
	  Arc * courrantArc;
	  for(i=0; i < g->listeArc->nb_elem; i++)
	    {
	      courrantArc = getDataIndice_Liste(g->listeArc, i);
	      if(comparer_Arc(arc, courrantArc) > 0)
		{
		  suppressionIndice_Liste(g->listeArc, i);
		  i --;
		}
	    }
	  suppressionCourant_Liste(g->listeNoeud);
	  detruire_Arc((void**)&arc);
	  testament_Noeud(&res);
	  return 0;
	}
      testament_Noeud(&res);
    }
  return 1;
  /* 1: noeud n'existe pas ; 0: noeud supprimer */
}

int suppressionGrapheNoeudParIndice(Graphe * g, const int indice)
{
  if(g)
    {    
      int i;
      Noeud * n = getDataIndice_Liste(g->listeNoeud, indice);
      if(n != NULL)
	{
	  Arc * arc = creer_Arc(0,n,n);
	  Arc * courrantArc;
	  for(i=0; i < g->listeArc->nb_elem; i++)
	    {
	      courrantArc = getDataIndice_Liste(g->listeArc, i);
	      if(comparer_Arc(arc, courrantArc) > 0)
		{
		  suppressionIndice_Liste(g->listeArc, i);
		  i --;
		}
	    }
	  suppressionIndice_Liste(g->listeNoeud, indice);	    
	  detruire_Arc((void**)&arc);
	  return 0;
	}
      fprintf(stderr, "erreur lors de la suppression du noeud");
    }
  return 1;
  /* 1: noeud n'existe pas ; 0: noeud supprimer */
}

int ajoutGrapheArcParNom(Graphe * g, const int v, const char* nom1, const char* nom2)
{
  if(g)
    {
      Arc * arc;
      Noeud n1, n2;
      Noeud *nA, *nB;
      init_Noeud(&n1, nom1);
      init_Noeud(&n2, nom2);
      arc = creer_Arc(v, &n1, &n2);
      if(chercheElem_Liste(&n1, g->listeNoeud) == 0)
	{
	  fprintf(stdout,"le premier noeud n'existe pas");
	  testament_Noeud(&n1);
	  testament_Noeud(&n2);
	  detruire_Arc((void **)&arc);
	  return 2;
	}
      else
	{
	  nA = (Noeud *)getDataCourant_Liste(g->listeNoeud);
	}
      if(chercheElem_Liste(&n2, g->listeNoeud) == 0)
	{
	  fprintf(stdout,"le second noeud n'existe pas");
	  testament_Noeud(&n1);
	  testament_Noeud(&n2);
	  detruire_Arc((void **)&arc);
	  return 2;
	}
      else
	{
	  nB = (Noeud *)getDataCourant_Liste(g->listeNoeud);
	}
      if(chercheElem_Liste(arc, g->listeArc) == 3)
	{
	  suppressionCourant_Liste(g->listeArc);
	  detruire_Arc((void **)&arc);
	  arc = creer_Arc(v, nA, nB);
	  insereCourant_Liste(arc, g->listeArc);
	  testament_Noeud(&n1);
	  testament_Noeud(&n2);
	  detruire_Arc((void **)&arc);
	  return 1;
	}
      else
	{
	  detruire_Arc((void **)&arc);
	  arc = creer_Arc(v, nA, nB);
	  insereEnQueue_Liste(arc, g->listeArc);
	}
      testament_Noeud(&n1);
      testament_Noeud(&n2);
      detruire_Arc((void **)&arc);
    }
  return 0;
}

int ajoutGrapheArcParIndice(Graphe * g, const int v, const int i, const int j)
{
  if(g)
    {
      Arc * arc;
      Noeud *nA, *nB;
      nA = (Noeud*)getDataIndice_Liste(g->listeNoeud, i);
      nB = (Noeud*)getDataIndice_Liste(g->listeNoeud, j);
      if(nA == NULL || nB == NULL)
	{
	  fprintf(stderr, "l'un des noeuds n'existe pas");
	  return 2;
	}    
      arc = creer_Arc(v, nA, nB);
      if(chercheElem_Liste(arc, g->listeArc) == 3)
	{
	  suppressionCourant_Liste(g->listeArc);
	  insereCourant_Liste(arc, g->listeArc);
	  detruire_Arc((void**)&arc);
	  return 1;
	}
      else
	{
	  insereEnQueue_Liste(arc, g->listeArc);
	  detruire_Arc((void**)&arc);
	}
    }
  return 0;  
}

void afficheGraphe(Graphe * g)
{
  if(g)
    {
      int i, j;
      Noeud *n;
      Arc * compArc;
      Arc * courrantArc;
      for( i=0; i < g->listeNoeud->nb_elem; i++)
	{
	  n = getDataIndice_Liste(g->listeNoeud, i);
	  printf("%s : \n" , (char*)(n)->nom);
	  compArc = creer_Arc(0,n,n);
	  for( j=0; j < g->listeArc->nb_elem + 1; j++)
	    {
	      courrantArc = getDataIndice_Liste(g->listeArc, j);
	      if(comparer_Arc(compArc, courrantArc) == 1)
		{
		  printf("\tnoeud(s) de destination\n");
		  printf("\t\t%s d'un cout de  ", (char*)(courrantArc->destination->nom));
		  printf("%d\n", (int)(courrantArc->valeur));		 
		}
	      if(comparer_Arc(compArc, courrantArc) == 2)
		{
		  printf("\tnoeud(s) source\n");
		  printf("\t\t%s d'un cout de  ", (char*)(courrantArc->source->nom));
		  printf("%d\n", (int)(courrantArc->valeur));		 
		}
	    }
	  detruire_Arc((void**)&compArc);
	}
    }
}

void initFile(int *file, int *dist, int taille, int *nbFile)
{
  int i, j;
  int indMin = 0;
  for(i = 0; i < taille; i++)
    {
      if(dist[i] != -1)
	{
	  if(dist[indMin] != -1)
	    {
	      if(dist[i] < dist[indMin])
		indMin = i;
	    }
	  else
	    indMin = i;
	}
    }
  file[0] = indMin;
  for(i = 0, j = 1; i < taille; i++)
    {
      if(i != indMin)
	{
	  file[j] = i;
	  j++;
	}
    }
  (*nbFile) = taille;
}

int recupMin(int *file, int *nbFile)
{
  int ret = file[0];
  if((*nbFile) != 0)
    file[0] = file[(*nbFile) - 1];
  (*nbFile) --;
  return ret;
}

void placeMin(int *file, int *dist, int nbFile)
{
  int indiceMin = 0;
  int i; 
  for(i = 0; i < nbFile; i++)
    {
      if(indiceMin != i)
	{
	  if(dist[file[indiceMin]] == -1)
	    {
	      indiceMin = i;
	    }
	  else
	    {
	      if(dist[file[i]] != -1)
		{
		  if(dist[file[i]] < dist[file[indiceMin]])
		    indiceMin = i;
		}
	    }
	}
    }
  if(indiceMin != 0)
    {
      int tmp = file[0];
      file[0] = file[indiceMin];
      file[indiceMin] = tmp;
    }
}

void Dijkstra(const Graphe * g, const int s)
{

  int i;
  int taille = 0;
  int nbFile = 0;
  int * dist = NULL;
  int * pred = NULL;
  int * file = NULL;
  Noeud  * nIndice = NULL;
  Noeud * n = NULL;

  taille = g->listeNoeud->nb_elem;
  dist = (int*)malloc(taille * sizeof(int));
  pred = (int*)malloc(taille * sizeof(int));
  file = (int *) malloc (taille * sizeof(int));

  n = getDataIndice_Liste(g->listeNoeud, s);

  if(n != NULL)
    {
      for(i=0; i < taille; i++)
	{
	  if(i != s)
	    dist[i] = -1;
	  else
	    dist[i] = 0;
	  pred[i] = -1;	  
	}
    }
  else
    return;
  initFile(file, dist, taille, &nbFile);
  /* Traitement Dijkstra */
  while(nbFile != 0)
    {
      i = recupMin(file, &nbFile);
      if(dist[i] != -1)
	{
	  nIndice = getDataIndice_Liste(g->listeNoeud, i);
	  if(testEstVide_Liste(g->listeArc) == 0)
	    {
	      premier_Liste(g->listeArc);
	      do
		{
		  Arc *arc = getDataCourant_Liste(g->listeArc);
		  if(comparer_Noeud(arc->source, nIndice) == 1)
		    {
		      Noeud *dest = arc->destination;
		      int iDest = getIndiceData_Liste(dest, g->listeNoeud);

		      if(dist[iDest] != -1)
			{
			  if(dist[iDest] > dist[i] + arc->valeur)
			    {
			      dist[iDest] = dist[i] + arc->valeur;
			      pred[iDest] = i;
			    }
			}
		      else
			{
			  dist[iDest] = dist[i] + arc->valeur;
			  pred[iDest] = i;
			}
		    }
		}
	      while(suivant_Liste(g->listeArc) == 1);
	    }
	  placeMin(file, dist, nbFile);
	}
      
    }  
  /* Affichage */
  printf("Noeud %s : \n", n->nom);
  for(i=0; i < taille; i++)
    {
      nIndice = getDataIndice_Liste(g->listeNoeud, i);
      if(n != nIndice)
	printf("\tNoeud %s : d'un cout de %d \n", nIndice->nom, dist[i]);
    }
  /* Libération */
  free(dist);
  free(pred);
  free(file);
  dist = NULL;
  pred = NULL;
}
